package com.nanbei.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * @ClassDescription: 桶排序·1
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/6/28 11:18
 */
public class BucketSort {

    public static void main(String[] args) {
        int[] ints = {11,43,34,21,54,100,6, 1, 3, 2, 4, 5, 9, 7, 8,10};

        int[] bubbling = countSort(ints);
        System.out.println(Arrays.toString(bubbling));
    }

    /**
     *
     * @param nums 待排序数组
     * @return 排序后的数组
     */
    public static int[] countSort(int[] nums) {
        int max = nums[0];
        int min = nums[0];
        for (int num : nums) {
            if (max < num) {
                max = num;
            }
            if (min > num) {
                min = num;
            }
        }
        // 希望每个桶中存放的数量
        double sqrt = Math.sqrt(max-min);
        int range = (int)Math.ceil(sqrt);

        ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
        // 寻找到最大和最小值以后来判断创建桶的个数
        for (int i = 0; i < (max - min) / range +1; i++) {
            arrayLists.add(new ArrayList<>());
        }

        // 将每个数值放到对应的桶中
        for (int num : nums) {
            int i = (num-min) / range;
            ArrayList<Integer> arrayList = arrayLists.get(i);
            arrayList.add(num);
        }

        // 对每个桶的元素进行排序
        for (ArrayList<Integer> arrayList : arrayLists) {
            arrayList.sort(Comparator.comparingInt(a -> a));
        }

        int index = 0 ;
        // 将已排序桶的数据存放到对nums数组当中
        for (ArrayList<Integer> arrayList : arrayLists) {
            for (Integer integer : arrayList) {
                nums[index++] = integer;
            }
        }

        return nums;

    }
}
